package com.hardy.newSolutionAlgorithm;

/**
 * Author: fuxh3@lenovo.com
 * Date: Created in 2017/12/26 0026
 * 在数组中查询第k小的元素
 */
public class FindKSmall {
    public static void main(String[] args) {
        int[] arr = {3,4,6,1,67,34,56};
        System.out.println(top(4,arr,0,arr.length-1));
        System.out.println(arr[top(4,arr,0,arr.length-1)]);

    }
    public static int partition(int[] arr,int l,int r){
        int p=arr[l];
        while(l<r){
            while (l<r&&arr[r]>=p){
                r--;
            }
            arr[l]=arr[r];
            while (l<r&&arr[l]<=p){
                l++;
            }
            arr[r]=arr[l];
        }
        arr[l]=p;
        return l;
    }
    public static int top(int k,int[] arr,int l,int r){
        int p;
        if(l<r){
            p=partition(arr,l,r);
            if(p-l+1==k){
                return p;
            }
            return k<p-l+1?top(k,arr,l,p):top(k-p+l-1,arr,p+1,r);
        }
        return -1;
    }
}
